package Leetcode.Stack;

import java.util.*;

/**
 * @Author: kirito
 * @Date: 2024/4/14 12:15
 * @Description:
 *
 * 股票价格跨度
 * 已解答
 * 中等
 * 相关标签
 * 相关企业
 * 设计一个算法收集某些股票的每日报价，并返回该股票当日价格的 跨度 。
 *
 * 当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
 *
 * 例如，如果未来 7 天股票的价格是 [100,80,60,70,60,75,85]，那么股票跨度将是 [1,1,1,2,1,4,6] 。
 *
 * 实现 StockSpanner 类：
 *
 * StockSpanner() 初始化类对象。
 * int next(int price) 给出今天的股价 price ，返回该股票当日价格的 跨度 。
 *
 *
 * 示例：
 *
 * 输入：
 * ["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
 * [[], [100], [80], [60], [70], [60], [75], [85]]
 * 输出：
 * [null, 1, 1, 1, 2, 1, 4, 6]
 *
 * 解释：
 * StockSpanner stockSpanner = new StockSpanner();
 * stockSpanner.next(100); // 返回 1
 * stockSpanner.next(80);  // 返回 1
 * stockSpanner.next(60);  // 返回 1
 * stockSpanner.next(70);  // 返回 2
 * stockSpanner.next(60);  // 返回 1
 * stockSpanner.next(75);  // 返回 4 ，因为截至今天的最后 4 个股价 (包括今天的股价 75) 都小于或等于今天的股价。
 * stockSpanner.next(85);  // 返回 6
 */

public class StockSpanner {
/*
    //这样写的话会发现每次都要循环遍历前面的元素，有很多遍历都是重复的
    //所以可以用一个结构将之前的天数存下来，方便get。
    List<Integer> list;
    public StockSpanner() {
        list = new ArrayList<>();
    }

    public int next(int price) {
        list.add(price);
        int size = list.size();
        int ans = 0;
        //这里每次都会重复循环以前遍历过的元素
        for (int i = size - 1; i >= 0; i--) {
            if (list.get(i) <= price) {
                ans++;
            }else{
                break;
            }
        }
        return ans;
    }
    */
//    List<Integer> list;
//    List<Integer> temp;
//    int pre = 0;
//    int count = 0;
//    public StockSpanner() {
//        list = new ArrayList<>();
//        temp = new ArrayList<>();
//    }
//
//    public int next(int price) {
//
//        if (count <= price) {
//            pre++;
//            count = price;
//        }else{
//            count = price;
//            return 1;
//        }
//        return pre;
//        list.add(price);
//        int size1 = list.size();
//        int size2 = temp.size();
//        int ans = 0;
//        for (int i = size1 - 1; i >= 0; i--) {
//            if (list.get(i) <= price) {
//                ans++;
//            }else{
//                break;
//            }
//        }
//        return ans;
//    }

// 双向队列（Deque），用于存储索引和价格的数组对。
// 第一个元素是虚拟的，其索引为-1，价格为Integer.MAX_VALUE，用于初始化堆栈。
    Deque<int[]> stack;
    int idx;

    public StockSpanner() {
        // 初始化双向队列和一个索引变量
        stack = new ArrayDeque<int[]>();
        stack.push(new int[]{-1, Integer.MAX_VALUE}); // 添加虚拟元素
        idx = -1; // 初始化索引变量为-1
    }

    // 该方法用于处理输入的价格，并返回在这个价格之前的连续上升价格天数
    public int next(int price) {
        idx++; // 增加当前索引
        while (price >= stack.peek()[1]) {
            // 当当前价格大于等于栈顶元素的价格时，弹出栈顶元素
            stack.pop();
        }
        // 计算当前价格之前的连续上升价格天数，即当前索引减去栈顶元素的索引
        //对对对，我就是差这一步想法，虽然之前连续上升不一定满足，但是可以减去他，然后继续判断
        int ret = idx - stack.peek()[0];
        // 将当前价格和索引压入栈中
        stack.push(new int[]{idx, price});
        // 返回连续上升价格的天数
        return ret;
    }

    /**
     * 75
     * 60
     * 70
     * 60
     * 80
     * 100
     */
    public static void main(String[] args) {
        StockSpanner stockSpanner = new StockSpanner();
        System.out.println(stockSpanner.next(100));
        System.out.println(stockSpanner.next(80));
        System.out.println(stockSpanner.next(60));
        System.out.println(stockSpanner.next(70));
        System.out.println(stockSpanner.next(60));
        System.out.println(stockSpanner.next(75));
        System.out.println(stockSpanner.next(85));
    }
}
